#ifndef __TWITTER__
#define __TWITTER__
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<queue>

using namespace std;

class Twitter {
private:
    static int timestamp;
    class User;
    class Tweet;
    map<int, User*> userMap;
    friend struct cmp;
public:
    /** user 发表一条 tweet 动态 */
    void postTweet(int userId, int tweetId, string text);
    
    /** 返回该 user 关注的人（包括他自己）最近的动态 id，
    最多 10 条，而且这些动态必须按从新到旧的时间线顺序排列。*/
    vector<int> getNewsFeed(int userId, int num);

    /** follower 关注 followee，如果 Id 不存在则新建 */
    void follow(int followerId, int followeeId);

    /** follower 取关 followee，如果 Id 不存在则什么都不做 */
    void unfollow(int followerId, int followeeId);

};

class Twitter::Tweet{
private:
    int time;
    int id;
    string text;
    Tweet* next;
    friend class Twitter;
    friend class User;
    friend struct cmp;
public:
    Tweet(){}
    Tweet(int t, int i, string txt): time(t), id(i), text(txt), next(nullptr){}
    
};

int Twitter::timestamp = 0;

class Twitter::User{
private:
    int id;
    set<int> followed;
    Tweet* head;
    friend class Twitter;

public:
    User(int i): id(i), followed(set<int>()), head(new Tweet()){follow(id);} 

    void follow(int userId) {
        followed.insert(userId);
    }

    void unfollow(int userId) {
        // 不可以取关自己
        if (userId != this->id)
            followed.erase(userId);
    }

    void post(int tweetId, string text) {
        Tweet* twt = new Tweet(Twitter::timestamp, tweetId, text);
        timestamp++;
        // 将新建的推文插入链表头
        // 越靠前的推文 time 值越大
        twt->next = head->next;
        head->next = twt;
    }
};

inline
void Twitter::postTweet(int userId, int tweetId, string text) {
    // 若 userId 不存在，则新建
    if (!userMap.count(userId))
        userMap.insert(make_pair(userId, new User(userId)));
    User* u = userMap[userId];
    u->post(tweetId, text);
}

/** follower 关注 followee */
inline
void Twitter::follow(int followerId, int followeeId) {
    // 若 follower 不存在，则新建
    if(!userMap.count(followerId)){
        User* u = new User(followerId);
        userMap[followerId] = u;
    }
    if(!userMap.count(followeeId)){
        User* u = new User(followeeId);
        userMap[followeeId] = u;
    }

    userMap[followerId]->follow(followeeId);
}

/** follower 取关 followee，如果 Id 不存在则什么都不做 */
inline
void Twitter::unfollow(int followerId, int followeeId) {
    if (userMap.count(followerId)) {
        User* flwer = userMap[followerId];
        flwer->unfollow(followeeId);
    }
}

struct cmp{
    bool operator()(Twitter::Tweet* a, Twitter::Tweet* b){
        return a->time < b->time;
    }
};

/** 返回该 user 关注的人（包括他自己）最近的动态 id，
最多 10 条，而且这些动态必须按从新到旧的时间线顺序排列。*/
inline
vector<int> Twitter::getNewsFeed(int userId, int num) {
    vector<int> ans;
    if(userMap.count(userId) == 0)
        return ans;
    
    priority_queue<Tweet*, vector<Tweet*>, cmp> pq;
    
    auto all_followed = userMap[userId]->followed;
    for(auto id: all_followed){
        auto twt = userMap[id]->head;
        if(twt != nullptr)
            pq.push(twt);
    }
    while(!pq.empty() && ans.size() < num){
        auto twt = pq.top();
        pq.pop();
        ans.push_back(twt->id);
        if(twt->next != nullptr)
            pq.push(twt->next);
    }
    return ans;
    
}



#endif
